package leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 合并k个升序链表
 */
public class Solution23 {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length ==0){
            return null;
        }
        if(lists.length ==1){
            return lists[0];
        }
        ListNode merge  = lists[0];
        for (int i = 1; i < lists.length; i++) {
            ListNode temp = lists[i];
            ListNode tempHeader = temp;
            ListNode mergeHead = merge;
            ListNode compareResult = new ListNode(-1);
            ListNode compareResultHead =compareResult;
            while(mergeHead!=null && tempHeader!=null){
                if(tempHeader.val <=mergeHead.val){
                    compareResultHead.next = tempHeader;
                    tempHeader = tempHeader.next;
                }else{
                    compareResultHead.next = mergeHead;
                    mergeHead = mergeHead.next;
                }
                compareResultHead = compareResultHead.next;
            }
            if(mergeHead!=null){
                compareResultHead.next = mergeHead;
            }
            if(tempHeader!=null){
                compareResultHead.next = tempHeader;
            }
            merge = compareResult.next;
        }
        return merge;
    }

    public ListNode mergeKListsQueue(ListNode[] lists) {
        if(lists == null || lists.length ==0){
            return null;
        }
        if(lists.length ==1){
            return lists[0];
        }
        PriorityQueue<ListNode> listNodePriorityQueue = new PriorityQueue<>(Comparator.comparingInt(v -> v.val));
        for (ListNode list : lists) {
            if (list != null) {
                listNodePriorityQueue.add(list);
            }
        }
        ListNode result = new ListNode(-1);
        ListNode resultHead = result;
        while(!listNodePriorityQueue.isEmpty()){
            ListNode poll = listNodePriorityQueue.poll();
            resultHead.next = poll;
            if(poll.next!=null){
                listNodePriorityQueue.add(poll.next);
            }
            resultHead = resultHead.next;
        }
        return result.next;
    }

}
